package demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    int ans = -1;
    boolean[] visited ;
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            children.get(edge[0]).add(edge[1]);
            children.get(edge[1]).add(edge[0]);
        }
        visited = new boolean[n];
        return dfs(0,children,coins,k,0,visited);
    }
    private int dfs(int cur,List<List<Integer>> children,int[] coins,int k,int div,boolean[] visited){
        // if (memo[i][j] != -1) { // 之前计算过
        //     return memo[i][j];
        // }
        if(visited[cur]){
            return 0;
        }
        visited[cur] = true;
        int res1 = (coins[cur] >> div) - k;
        int res2 = coins[cur] >>(div+1);
        for(int child :children.get(cur)){
            //方法一
            res1+=dfs(child,children,coins,k,div,visited);
            //方法二
            res2+=dfs(child,children,coins,k,div+1,visited);
        }
        visited[cur] = false;
        return Math.max(res1,res2);
    }

    public String findLatestTime(String s) {
        // 字符串
        char[] c = s.toCharArray();
        int n = c.length;
        if (c[4] == '?')
            c[4] = '9';
        if (c[3] == '?')
            c[3] = '5';
        if (c[1] == '?') {
            if (c[0] == '0')
                c[1] = '9';
            else
                c[1] = '1';

        }
        if (c[0] == '?') {
            if (c[1] >= '2')
                c[0] = '0';
            else
                c[0] = '1';
        }
        return new String(c);
    }

    public int minCount(int[] coins) {
        int res = 0;
        for (int coin: coins) {
            res += (coin + 1) / 2;
        }
        return res;
    }
}
